/*
 *  Copyright (c) 2011 Mathew Hall.
 *  All rights reserved.
 * 
 *  Redistribution and use in source and binary forms, with or
 *  without modification, are permitted provided that the following conditions
 *  are met:
 * 
 *  Redistributions of source code must retain the above copyright
 *  notice, this list of conditions and the following disclaimer.
 *  Redistributions in binary form must reproduce the above
 *  copyright notice, this list of conditions and the following
 *  disclaimer in the documentation and/or other materials provided
 *  with the distribution.
 *  Neither the name of the University of Sheffield nor the names of its
 *  contributors may be used to endorse or promote products derived
 *  from this software without specific prior written permission.
 * 
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 *  CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 *  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 *  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 *  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 *  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 *  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 *  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 *  EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package search.fitnessfunctions.util

import primitives.cluster.*;
import primitives.graph.*;
import search.fitnessfunctions.util.*;

import static search.fitnessfunctions.util.CRTuple.*

/**
 *  
 * @author Mathew Hall
 */
abstract class EdgeSubsumptionTransformer {
    


    def static outEdges(IClusterLevel c){
        Collection<Transition> nodes = []
        c.nodes.each{
            node ->
            nodes.addAll(node.getTransitionsAsT().findAll{
                    trans -> 
                    !c.nodes.contains(trans.destinationNode)
              
                })
        }
        return nodes
    }

	def static commonOutEdges(IClusterLevel c){
		def allTs = outEdges(c)
		
		HashSet<CRTuple<String,Node>> trans = new HashSet<CRTuple<String,Node>>();
		
		allTs.each{
			transition ->
			def label = transition.label
			def to = transition.destinationNode
			
			def common = c.nodes.findAll{
				node ->
				
				//find at least one transition that has the same destination and label
				node.transitionsAsT.findAll{
					nodeT ->
					nodeT.label.equals(label) && nodeT.destinationNode.equals(to)
				}.size() > 0
				
			}.size() == c.nodes.size() //the set of nodes having this transition is the same size as all nodes in c
			if(common) trans.add(new CRTuple<String,Node>(transition.label,transition.destinationNode))
		}
		
		return trans;
		
	}
    
    static boolean  sameOutEdges(Collection<Node> nodes){
        //problem:
            //getNodes returns set of nodes in subclusters too, although
            //subsupmption should be tried top-down rather than iteratively.
        Set<Node> outs = new HashSet<Node>();
        nodes.each{outs.addAll(it.transitionsAsN)}
        
        def toRemove = []
        
        outs.each{
            if(nodes.contains(it)) toRemove.add(it)
        }
        
        toRemove.each{
            outs.remove(it)
        }
        return nodes.each{
            outs.containsAll(it.transitionsAsN)
        }.find{!it} == null
        //if any of these is false, find will find it and return it (shorthand for it == false)
        //otherwise it will return null, checking for == null converts to boolean.
        //workaround of missing all() method - return true iff all elements evaluate to true.
    }
    
    
    def static subsumeNodeInClustered(IClusterLevel c, ClusterHead tree){
        
        Node replacement = new Node("\"Subsume[" + c.nodes.collect{it.label}.join('_') + "]\"")

  
        /**/
        tree.nodes.each{
            node ->
            def newTrans = []
            def trns = node.transitionsAsT
            trns.each{
                transition ->
                if(c.nodes.contains(transition.destinationNode)){
                    //target node for a transition is subsumed in replacement, so rewrite:
                    node.deleteTransition(transition)
                    def lbl = transition.label
                    node.connect(replacement,lbl)
                }
            }
           
        }
        
       c.nodes.each{
            //subsumed node needs to point at each trans from c.nodes
            it.transitionsAsT.each{
                transition ->
                replacement.connect(transition.getDestinationNode(),transition.getLabel())
                
            }
            

        }
        

        //Every transition in the graph now points to the replacement
        c.nodes.each{
            //subsumed node needs to point at each trans from c.nodes
           
            
            c.removeNode(it)
            

        }//*/
        
        //Old nodes are now gone
        c.addNode(replacement)
        
 
        
        
    
    }
    
    def static allSubmods(ClusterHead tree){
        def modules = [];
        
        tree.getChildren().each{if(it.encapsulates()) modules.add(it)}
        
        ClusterNode current; // = modules.first();
        
        def curr = 0;
        while (curr < modules.size()){
            current = modules.get(curr)
            modules.addAll(current.children.findAll{it.encapsulates()})
            curr++
        }
        return modules;
    }

	def static subsumeEdgesOfCluster(IClusterLevel c, ClusterHead tree){
        
        def commonOuts = commonOutEdges(c);
        
		commonOuts.each{
			t ->
			def label = t.fst()
			def to = t.snd()
			c.nodes.each{
				node -> 
				node.transitionsAsT.findAll{
					tran ->
					tran.label == label && 	tran.destinationNode == to
				}.each{
					node.deleteTransition(it)
				}
			}
			c.nodes.find{true}.each{
				it.connect(to,label,true) 
				//println "Done an edge merge"
			}
		}

 
        
        
    
    }
    
    
    def static transform(ClusterHead tr){
	

		def tree = tr.deepCopy()
        Queue smods = new LinkedList(tree.children)
        while(!smods.isEmpty()){
            def mod = smods.remove()

            if(mod.nodes.size() > 1){
                subsumeEdgesOfCluster(mod,tree)
            }else{
                if(mod.encapsulates()){
                    smods.addAll(mod.children)
                }
            }

        }
        return tree
    }
}

